Simultaneous mobility is the special case when two end (or terminal) hosts (Mobile Hosts) in a communications session through a network are mobile and both move from one attachment point in the network to another at or about the same time. Although it may not be typical (more typical would be the case when one of the two hosts moves and the other hosts within the network remain stationary during that time), such an event will occur in infrastructure-based networks and this must be handled properly by mobility protocols. This simultaneous mobility problem results in the loss of to a binding update from one Mobile Host because it is sent to a previous address of the other Mobile Host that is also moving at around the same time.
Two Mobile Hosts attached to attachment points nodes in an ad hoc network are in a “communication session” if they are actively exchanging data. A communication session may be in a “normal state” or an “interrupted state.” A session is in a normal state when data from one Mobile Host is arriving at the right location for the other Mobile Host, and vice versa. It is in an interrupted state otherwise.
A handoff is a movement of a Mobile Host from a previous attachment point to a new attachment point. The “handoff time” is the moment in time when it changes from being reachable at the previous attachment point to being not reachable at the previous attachment point. Given that time is continuous, it is assumed that only one handoff can occur at any given moment in time, i.e, that handoff times are unique. Two handoffs are consecutive if neither of the Mobile Hosts performs another handoff in between the two handoffs. Consecutive handoffs can be at the same mobile host or between two different mobile nodes.
FIG. 13 depicts the simultaneous mobility of two mobile hosts 1300 and 1305 in an infrastructure based network. The example network in FIG. 13 is comprised of backbone routers 1310a, 1310b and border routers 1320a-g, 1340a-d, 1360a-d and 1380a-f in each of four border domains. At the edge of each border domain attachment points 1330a-e, 1350a-e, 1370a-f and 1390a-e permit mobile hosts 1300 and 1305 to attach. The simultaneous mobility problem arises when mobile host 1300 moves from attachment point 1330a to attachment point 1350b in domain2 for example while at the same (or nearly the same) time mobile host 1305 moves from attachment point 1390b to attachment point 1370a. The binding update information that must be passed between mobile host 1300 and mobile host 1305 will not reach the other prior to their movement.
A binding update is information about the location of the sending Mobile Host. A binding update is “lost” if it does not arrive at its intended recipient Mobile Host. A binding update makes a “belated arrival” if it arrives at a network where the destination address used to be valid for the intended recipient Mobile Host but it is no longer valid at the moment of arrival. A binding update is “lost through belated arrival” if it makes a belated arrival and is consequently lost. Binding updates do not contain information about future moves of the sending Mobile Host. While two Mobile Hosts are in a communication session, they get information on the location of the other Mobile Host only from binding updates. In other words, they do not actively seek the location of the other Mobile Host, but only passively accept binding updates. Binding updates are sent directly to the most current known address (known by the sender) of the intended recipient Mobile Host. In general, the latency for binding updates to arrive is assumed to be much smaller than the average inter-handoff time, therefore, it is extremely unlikely that a binding update would be sent and the recipient Mobile Host would move twice before the binding update arrives at the previous network of the recipient.
Standard Mobile Internet Protocol (MIP) does not have a problem with simultaneous mobility. By design, non-moving Correspondent Hosts are unaware of the mobility of Mobile Hosts. The home agent of the Mobile Host functions as an anchor point for the Mobile Host. No matter where the Mobile Host moves, packets for it always go first to its home network for interception and tunneling by its home agent. If it turns out that the Correspondent Host is also mobile, it will also have a home agent and packets from the Mobile Host will similarly be intercepted and tunneled to the appropriate network by its home agent. Since both home agents are stationary and can always be reached through IP routing simultaneous mobility does present a problem to MIP. The standard MIP protocol, however, does not have the survivability features of SIP, MIP-LR or MIPv6. There has been suggestion to extend TCP migration mobility protocol to handle simultaneous mobility, but there are significant differences between the TCP migration schemes (where mobility is handled at the transport layer) and MIP-related or SIP that can be taken care of at the application layer.
Session Initiation Protocol (SIP) is a protocol that enables setting up voice calls, two-way multimedia sessions, teleconferencing, instant messaging and other types of communication using the Internet. SIP is a protocol in the Application Layer of the OSI Reference Model to enable the establishment, management and termination of such real-time communications sessions over an Internet Protocol (IP) network. SIP is defined by RFC 3261 of the Internet Engineering Task Force (IETF). SIP negotiates the features and capabilities of a communication session at establishment of the session reducing time necessary for setting up communication sessions. Mobility of the end host is handled very naturally by SIP using existing SIP signaling mechanisms. For example, to initiate a session, the SIP “INVITE” message is sent by the initiating device to the other device. The extension of SIP to handle mid-session mobility specifies that when one of the two devices moves, it sends a re-INVITE message to the other device, informing it of its new location (e.g., its new IP address). In addition to the re-INVITE message sent directly to the device that moved (Mobile Host) to the other device (Correspondent Host), the Mobile Host also registers its presence in the new network with a SIP server in its home network. This allows other potential Correspondent Hosts to find the Mobile Host.
FIG. 1 depicts the movement of a Mobile Host from one “foreign” network to another. Mobile Host 112 moves from foreign subnet 110a to foreign subnet 110b which are both away from the home network 100 where the SIP server 102 for Mobile Host 112 resides. Corresponding Host 122 resides in subnet 120. Step 1 (each step is indicated by the lines with arrows and bold single digit reference numerals) is the movement of Mobile Host 112 from subnet 110a to subnet 110b. After movement to a new subnet the Mobile Host 112 sends a re-INVITE message to Corresponding Host 122 at step 2. At step 3, Corresponding Host 122 sends a SIP OK message to Mobile Host 112. Mobile Host 112 and Corresponding Host 122 can then exchange data at step 4. At step 5 the relocated Mobile Host registers with the SIP Server 102 at its home network 100.
FIG. 2 is a diagram depicting the flow of data resulting from a mishandling of simultaneous mobility in SIP. In the basic SIP mobility scheme, when a Mobile Host moves to a new network, it sends a re-INVITE message to the Correspondent Host, as well as a REGISTER message to its home network SIP server. There are two options for the part of the re-INVITE, i.e., it could go through the inbound proxy of the Correspondent Host, or it could go directly to the Correspondent Host. This second option will not work properly if there is simultaneous mobility of the Mobile Host and the Correspondent Host. Clearly, if the Correspondent Host moves at the same time, the re-INVITE may be lost (and similarly, the re-INVITE from the Correspondent Host to the Mobile Host could also be lost). As the home SIP severs for both are stationary and always reachable through IP routing, the registrations are not affected by simultaneous mobility. It would appear the both hosts could now obtain the new location of the other party through the SIP servers, analogous to how the home agent provides such information in MIP. However, in MIP, the home agent quickly discovers that the Correspondent Host needs the updated binding information, because data packets from the Correspondent Host are routed to the home network and intercepted by the home agent. In the SIP case, on the other hand, the Correspondent Host may not immediately contact the SIP sever. Instead the re-INVITE may time-out and may be tried again several more times to the wrong network by virtue of its built-in retransmission mechanism. The crucial difference is that the data path and signaling path are separate in the case of SIP, unlike that of MIP. For simplicity, automatic retransmissions of lost re-INVITE messages are not shown and neither are messages like ACK that acknowledge the SIP OK.
Simultaneous mobility of two end-hosts is not usually an issue for pre-session mobility in SIP. However, during a transition before a SIP session set-up is complete, simultaneous mobility may present problems. As shown in FIG. 3, it may so happen that one of the signaling messages (INVITE, OK, ACK) does not reach the other party and gets lost, despite the SIP server keeping an up-to-date registration for both parties.
Mobile IP with Location Registers (MIP-LR) is an extension of the Mobile IP protocol. Mobile IP is an extension to basic Internet Protocol (IP) intended to serve mobile users of IP devices (known as Mobile Hosts) enabling them to roam across networks and geographies while remaining connected as if attached to the home location of the Mobile Host device. In Mobile IP a Mobile Host has one permanent address for identification and acquires a temporary card-of-address (COA) for routing purposes. Data is transmitted to the permanent address associated with the Mobile Host device. When the Mobile Host device is away from its permanent address the “home agent” at the permanent address forwards the data packets in care of the “foreign agent” by encapsulating the data with another IP address contained in a data header preceding the original packet. Upon receipt of the data packets by the “foreign agent” the additional header is removed through a “decapsulation” process. If the device relocates again, the “home agent” and the current “foreign agent” are notified and packets en route can be rerouted to a new “foreign agent” through a process known as “smooth handoff.” MIP requires registration messages be exchanged with a home agent on a Mobile Host's home network whenever the Mobile Host moves between subnets in foreign networks, to ensure that the home agent can tunnel packets destined for the Mobile Host to the right foreign agent in the foreign subnet. With MIP, all packets sent to the Mobile Host have to pass through the home agent, making the home agent a single point of failure. This is a serious problem for networks that require high levels of robustness and survivability.
In Mobile IP with Location Registers (MIP-LR) the sender first queries a database called a Location Register (or Home Location Register) in order to obtain the current location of the recipient device or Mobile Host. MIP-LR was designed for use in tactical military environments, enterprise environments and within logical administrative domains because it requires that a sending host be aware which host implements the MIP-LR protocol. MIP-LR is interoperable with MIP. Hosts that implement only MIP can continue to operate but will not gain the benefit of MIP-LR.
In MIP-LR, when a Mobile Host moves from one subnet to another, it registers its current forwarding care-of-address (COA) with a database called a Home Location Register (HLR). When a Correspondent Host has a packet to send, it first queries the HLR to obtain the COA of the Mobile Host and then the Corresponding Host sends the packet directly to the Mobile Host. Mapping from the Mobile Host's permanent IP address to its COA is done by the IP layer at the Correspondent Host and is transparent to higher-layer protocols. The reverse mapping is done at the Mobile Host. The Correspondent Host caches the Mobile Host's COA to avoid querying the HLR for every subsequent packet destined for the Mobile Host. The Mobile Host maintains a list of Correspondent Hosts with which it is in active communication and informs them if it moves to a different subnet as is done in Mobile IP. Unlike the home agent in MIP, a home location register need not necessarily be located in the home network and it can be replicated for survivability. FIG. 4 is a diagram depicting mobility of a Mobile Host in a network employing MIP-LR. At step 1 Mobile Host 412 connected to foreign subnet 410 which has a visitors location register (VLR) 460 associated with it resisters its care-of-address (COA) with its HLR 450 associated with its home network 400. At step 2 the Corresponding Host 422 queries the HLR 450 to find the current COA for Mobile Host 412. At step 3 the HLR sends the COA for Mobile Host 412 to Corresponding Host 422. At step 4 the Corresponding Host caches the COA of the Mobile Host and at step 5 the Corresponding Host sends un-encapsulated data packets directly to the COA for the Mobile Host.
FIG. 5 is a diagram depicting the flow of data resulting from simultaneous mobility in networks implementing MIP-LR. The problem that MIP-LR faces with simultaneous mobility are analogous to the problems faced by SIP with simultaneous mobility when SIP re-INVITES are sent to mobile Correspondent Hosts. When a Mobile Host moves to a new network, it sends a MIP-LR update message to the Correspondent Host, as well as a MIP-LR update to its Home Location Register (HLR). Clearly, if the Correspondent Host moves at the same time, the direct MIP-LR update may be lost (and similarly, the direct MIP-LR update from the Correspondent Hosts to the Mobile Host could also be lost). Since the HLR's for both hosts are stationary and always reachable through IP routing, the registrations should not be affected by the simultaneous mobility. However, like in the SIP case described above, the Correspondent Host may not immediately query the HLR and both hosts will be using out-dated IP addresses for each other.
Another issue of simultaneous mobility arises with respect to MIPv6 the extension of MIPv4. Mobile IP (MIPv4) is the dominant mobility-handling protocol for host mobility on the Internet. However, with the rise of Internet Protocol version 6 (IPv6), a new mobility-handling protocol was needed for host mobility on IPv6 networks. The new protocol, proposed by the Internet Engineering Task Force (IETF) is Mobile IPv6 (MIPv6). Among the new features introduced with MIPv6 is route optimization (MIPv4 also had a way to do route optimization, but route optimization for MIPv4 was always a “draft-stage” add-on and never part of the main MIPv4 specifications). Route optimization has its benefits, but a major problem is that it makes MIPv6 vulnerable to the simultaneous mobility problem. Since 3G wireless specifications groups are moving towards IPv6, and beyond-3G systems are even more likely to use IPv6, the vulnerability of MIPv6 to the simultaneous mobility problem becomes a critical issue.
Directly providing binding updates from the Mobile Host to the Corresponding Host pose a security problem. In the case of the home agent, it is reasonable to stipulate that the Mobile Host and home agent should have an IPsec security association, but it is not reasonable to stipulate the same between the Mobile Host and every potential Corresponding Host. The solution adopted in MIPv6 is to use the so-called “return routability” procedure. This allows the Mobile Host and Corresponding Host to set up a shared key in a “reasonably” secure manner.
Because timing is so important in analyzing the simultaneous mobility problem in MIPv6, there is a need to review the exact sequence of events that happens whenever a Mobile Host moves to a new foreign network. The typical sequence of events is as follows. In step 1, (if handing off from a previous network) the Mobile Host stops being reachable at the previous network. In step 2, the Mobile Host obtains a new care-of-address at the new foreign network. The Mobile Host initiates registration of its new care-of-address with its home agent at step 3. At step 4, the Mobile Host performs correspondent registration procedure with all its Correspondent Hosts (except those from which it may wish to keep its topographical location private). Registration with Correspondent Hosts consists of two sequential parts. First the return routability procedure is performed and then the authenticated binding update is sent using the shared key generated during the latest return routability procedure.
The Mobile Host must initiate registration of its new care-of-address with its home agent (by sending a Binding Update to the home agent) before it may perform any correspondent registration procedures related to the new care-of-address. However, it does not need to wait to see if the registration with the home agent is successful before performing correspondent registrations. The correspondent registration procedure, as specified by RFC 3775, always includes a return routability procedure before sending of binding updates to a Correspondent Host. This implies a Mobile Host that moves fast between foreign networks would have to go through a long correspondent registration procedure with each of its Correspondent Hosts every time it moves. This could be fairly disruptive to the packet flows from Correspondent Host to Mobile Host. However, RFC 3775 does specify an optional expedited return routability procedure.
In the return routability procedure, the Mobile Host sends two messages to the Correspondent Host; these are the Home Test Init and the Care-of Test Init messages. The Home Test Init is reversed tunneled to the home agent from the Mobile Host, and then forwarded by the home agent to the Correspondent Host. The Care-of Test Init is sent directly to the Correspondent Host. The Correspondent Host responds by sending a Care-of Test message directly to the Mobile Host, addressed to its care-of address, and by sending a Home Test message indirectly to the Mobile Host, addressed to its home address. The Care-of Test message contains the “care-of keygen token”, and the Home Test message contains the “home keygen token.”
The care-of keygen token and home keygen token are hashed together to form the “binding management key”, a shared secret key that can be used by the Mobile Host to send a binding update to the Correspondent Host. The Correspondent Host is the only node that can generate the care-of and home keygen tokens, since the generation of these tokens involves the “node key” of the Correspondent Host, where the node key is a secret key never shared with anybody, and whose value changes from time to time. Because the tokens are sent to the Mobile Host by two paths, it is most likely that only the Mobile Host would know both tokens. Thus, only the Correspondent Host and the Mobile Host can generate the correct binding management key, which is used to authenticate binding updates from the Mobile Host to the N to Correspondent Host.
RFC 3775 does not allow an Mobile Host to perform return routability once, generate the binding management key, and then re-use the key for subsequent binding updates (and furthermore, the correspondent registration procedure for each Correspondent Host proceeds independently, each with their own binding management key). Instead, a new binding management key must be derived each time a Mobile Host moves. However, RFC 3775 allows for an expedited process for deriving the key—a recent home keygen token can be re-used, with a new care-of keygen token.
In the expedited process, only a new care-of keygen token needs to be obtained, so the return routability procedure then consists of a Care-of Test Init message from the Mobile Host to the Correspondent Host, and the care-of keygen token being sent in response directly to the new care-of-address, in the Care-of Test message. This is expected to reduce correspondent registration latency in some cases, especially where the roundtrip through the home agent (for the Home Test Init and Home Test messages) may be significantly larger than the roundtrip directly between Mobile Host and Correspondent Host.
A problem arises when both the Mobile Host and the Correspondent Host are both mobile at the same time. When a Mobile Host moves to a new foreign network prior to, and including, step 3 (initiation of registration with the home agent), any movement of the other node does not matter. However, when it comes to step 4 (correspondent registration), the situation changes. Correspondent registration depends for its success upon messages reaching the other node. If the other node moves any time before receiving the binding update, one or more messages may be lost and the correspondent registration procedure may therefore fail. The messages lost may be during the return routability phase or after it. Two different cases are possible. First where messages are lost during the return routability procedures and secondly, where messages are lost after the return routability procedure.
In the first case, the two hosts are referred to as Mobile Host A and Mobile Host B. Mobile Host A moves, initiates home agent registration, and then initiates the return routability procedure with Mobile Host B. One or both of the Home Test Init and Care-of Test Init messages may be lost because of simultaneous movement by Mobile Host B. Now consider what happens to the correspondent registrations that Mobile Host B wishes to initiate with its Correspondent Hosts. Without receiving both the Care-of Test Init and Home Test Init from Mobile Host A, Mobile Host B will not update Mobile Host A's address in its cache, so Mobile Host B will send its Care-of Test Init and Home Test Init messages to Mobile Host A's old care-of-address. More precisely, Mobile Host B will send its Care-of Test Init message directly to Mobile Host A's old care-of-address, and reverse tunnel its Home Test Init to its home agent which will then forward it to Mobile Host A's old care-of-address. Thus, Mobile Host B will be unable to proceed with its own return routability procedure.
Basically, the scenario is that one of the Mobile Hosts moves first (say, Mobile Host A), but by the time Mobile Host B moves a little while later, one or both of the Home Test Init messages has not yet reached Mobile Host B, so Mobile Host A's return routability procedure never completes, which implies that Mobile Host B will also be unable to complete its return routability procedure. This scenario is depicted in the diagram in FIG. 6.
Now suppose that Mobile Host B did not move so soon after Mobile Host A moved, but only moved after Mobile Host A's return routability procedure has completed. Then Mobile Host A and Mobile Host B would have the binding management key for Mobile Host A to send an authenticated binding update to Mobile Host B. However, because of Mobile Host B's movement, Mobile Host A's binding update goes to Mobile Host B's old care-of-address and is lost. Meanwhile, Mobile Host B is trying to initiate Mobile Host B's return routability procedure, but both the Home Test Init and Care-of Test Init messages go to Mobile Host A's old care-of-address, and so are lost as well. This scenario is depicted in FIG. 7.
When a standard return routability procedure has been recently performed, a Mobile Host can re-use the home keygen token sent by a Correspondent Host. Thus, only the Care-of Test Init and Care-of Test messages need be exchanged in the expedited return routability procedure. Basically, the scenario is that one of the nodes moves first (say, Mobile Host A), but by the time Mobile Host B moves a little while later, the Care-of Test Init message has not yet reached Mobile Host B, so Mobile Host A's expedited return routability procedure never completes. This implies that Mobile Host B will also be unable to complete its return routability (whether expedited or not).
Thus, it is desirable to have a solution to the simultaneous mobility problem for SIP-based, MIP-LR-based and MIPv6-based mobility management schemes, particularly one using a common approach. It would be desirable to impose minimal changes on the existing protocols while efficiently dealing with the simultaneous mobility problems. Furthermore, it would be desirable to handle both pre-session and mid-session mobility focusing on layer 3 handoffs, i.e. where IP address changes are involved.
Although an additional problem could be created by having an excessive handoff rate this is not the focus of the present invention. The present invention is aimed at finding a solution to the simultaneous mobility problem where the handoff rate of a Mobile Host is “typical” enough that consecutive handoffs of the same Mobile Host are non-overlapping. This invention does not resolve situations of overlapping consecutive handoffs of the same Mobile Host, where one handoff has not completely finished before the next begins, e.g. there has not been enough time after the acquisition of an IP address for binding updates to reach their destination networks. The problems encountered with overlapping consecutive handoffs are caused by an excessive handoff rate which is different from the problem caused by simultaneous mobility. Whether the Correspondent Host is mobile or fixed, there will be very severe problems when the Mobile Hosts changes its IP address before binding updates for its previous IP address have even arrived at their destinations. For the foreseeable future, the extreme case of handoffs rates high enough for overlapping consecutive handoffs is highly improbable.